1. Field of the Invention
The invention relates generally to computer systems, and specifically to a computer system specially configured in support of solving NP-complete type problems of the polynomial difficulty.
2. Background of the Prior Art
It is known that a precise solution to an NP-complete type problem of discrete mathematics, such as the problem of finding the minimum Hamiltonian cycle in a Hamiltonian network, can be found by constructing all possible solutions of the problem and selecting the optimal solution among them. The problem with this method of constructing and comparing all possible solutions is that, since the number of possible solutions depends on the problems dimension N as N!, existing computers can construct and evaluate the set of possible solutions within a practical amount of time only in the case where N is sufficiently small. Significant time delays of up to several minutes and attendant component degradation are observed in the case where currently available computer systems are employed to solve moderate node sized minimal cycle problems (e.g. N=10-20) using the approach of constructing all possible solutions. As the number of nodes increases, computation time requirements increase exponentially. It is estimated that the fastest available computer system would require at least one month of computation time to precisely solve a simple 30 Node minimal Hamiltonian cycle problem wherein a primary network contains non-binary edge weights using a construct-all-solutions approach.
Currently available computer systems which claim to provide solutions to Hamiltonian cycle problems within a reasonable time employ methods having method steps based on approximations of exact solutions. Accordingly, these systems cannot be relied upon where an exact solution to an NP-complete type problem is required.
Other attempts have been made to model Hamiltonian networks using resistive circuits. Studies have shown that a minimum Hamiltonian cycle can be defined by Kirchoff""s equations. Nevertheless, as is the case with existing computer-implemented methods, problems have been noted in the accuracy attainable with methods based on physical modeling.
There exists then a need for a computer system configured to precisely solve NP-complete type problems such as Hamiltonian cycle problems within a practical time frame.
According to its major aspects and broadly stated, the present invention is a computer system comprising a microprocessor in communication with a memory space that is configured to precisely solve NP-complete type problems, including problems which, based on the number of nodes, have large dimensions. The computer system is configured to solve the minimal Hamiltonian cycle of a primary network comprised either of edges having non-binary (which may include positive and negative weights) or of binary (0 or 1) valued weights.
The computer-implemented method includes the steps of recording in a computer memory space a primary network represented by the matrix of its edge weights; forming an equivalent representation of the primary network as a set of N subnetworks; improving a path of the network by reordering the nodes of the path according to a predetermined set of reordering rules; transforming the set of subnetworks by changing weights in the subnetworks according to a predetermined set of edge weight changing rules; and repeating the improving and transforming steps until an exit condition is satisfied.
In the forming step for separating the primary network into N subnetworks, each subnetwork is formed by changing the weights of certain edges of the primary network so that, in each formed subnetwork, all edges incident to one node of the subnetwork have zero weight.
In the improvement step, a starting path, or ordering of nodes is selected, and improved by reordering the nodes of the network according to a predetermined set of reordering rules. The ordering of nodes after the first or any subsequent reordering is referred to as the present minimal path. In one variation of the improvement step, data from the first subnetwork is used while the path is subjected to a test wherein the weight of a connecting edge connecting a certain node of the path is compared to the edge weights of remaining non-incident edges of the present path. If the weight of the connecting edge is less than that of any remaining in the path, than the path is reordered so that the node connected by the connecting edge is interposed between the pair of nodes connected by the path edge having greater weight than the connecting edge. After the path is reordered considering the edge weights of the first subnetwork, the test is applied using the reordered cycle and the weights of the cycle of the second subnetwork. The improvement procedure continues until a termination condition is satisfied.
When the improvement procedure is complete, the edge weights of certain edges of each subnetwork are changed according to a set of edge weight changing rules in a transformation step according to the invention. In one variation of the transformation step, each subnetwork is subjected to a test wherein the weight of a connecting edge of an initial node of an improved path (as determined in the preceding improvement step) is compared to the edge weights of non-incident edges of the path. If the connecting edge has a weight greater or equal to the maximum edge weight of the remaining non-incident edges in the path, then edge weights of certain edges in the set of subnetworks are changed by an amount determined by the difference between the edge weights of certain connecting edges of the path. The edge weight changing procedure is carried out for each subnetwork of the set of subnetworks until a termination condition is satisfied.
The improvement step and the transformation step are repeated until an exit condition is satisfied. An exit condition is satisfied either if the present minimal path is not reordered on application of the set of reordering rules, or the edge weight of the edges of the set of subnetworks are not changed on application of the edge weight changing rules. When an exit condition is satisfied, the ordering of the present minimal path during the most recent application of the improvement step is stored in the computer system""s memory space as the minimal passage along the Hamiltonian cycle, and the sum of edge weights associated with the path is stored in the memory space as the value of the minimal Hamiltonian cycle.
A major advantage of the invention is that the computer implemented method dramatically reduces the computational time necessary to solve minimal Hamiltonian cycle problems, as compared to the only known alternative precise solution method involving constructing and comparing all possible solutions. As a result, the method frees up computer systems configured to solve minimal Hamiltonian cycle problems to perform other tasks, or to solve additional minimal Hamiltonian cycle problems within a given time frame. The dramatic reduction in the number of data transfers required to solve minimal cycle problems also significantly reduces computer component degradation resulting from the required data transfers.